package com.sequentialSearch

/**
 * @since 2018.5.3
 * @author 张一鸣
 * @version 0.1
 * 根据算法第四版，写一个基于链表的无序字典
 */
import java.util.ArrayList;

/**
 * 可以预见的是，效率会非常慢，
 * 插入特别快
 * 查询特别慢
 */
class SequentialSearchST<Key, Value> {
    private var first: Node? = null
    private var size = 0

    private inner class Node(internal var key: Key, internal var value: Value, internal var next: Node?)

    operator fun get(key: Key): Value? {
        var x = this.first
        while (x != null) {
            if (x.key == key) {
                return x.value
            }
            x = x.next
        }
        return null
    }

    fun put(key: Key, value: Value) {
        var x = this.first
        while (x != null) {
            if (key == x.key) {
                x.value = value
                return
            }
            x = x.next
        }
        this.first = Node(key, value, this.first)
        size += 1
    }

    fun keys():ArrayList<Key> {
        val keys = ArrayList<Key>()
        var x = this.first
        while (x != null) {
            keys.add(x.key)
            x = x.next
        }
        return keys
    }

    fun delete(key: Key) {
        var x = this.first
        while (x != null) {
            if (x.key == key) {
                this.first = x.next
                this.size -= 1
                return
            }
            x = x.next
        }
    }
}
